package Leetcode第二期;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : K k
 * @date : 14:34 2020/9/23
 * 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
 *
 * 给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 * [[1,1,0],
 *  [1,1,0],
 *  [0,0,1]]
 * 输出：2
 * 解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
 * 第2个学生自己在一个朋友圈。所以返回 2 。
 * 示例 2：
 *
 * 输入：
 * [[1,1,0],
 *  [1,1,1],
 *  [0,1,1]]
 * 输出：1
 * 解释：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。
 */
public class 朋友圈_547 {

    //思路:无向图
    //方法一：使用DFS 无向图则不需要将visited置回0,有向图则需要
    public int findCircleNum(int[][] M) {
        int[] visited=new int[M.length];
        int count=0;
        for(int i=0;i<M.length;i++){
            //三个人进行dfs搜索
            if (visited[i]==0){
                //若同一个人已经访问过一次则，朋友圈数量则减一
                dfsSolver(M,visited,i);
                count++;
            }
        }
        return count;
    }

    private void dfsSolver(int[][] M, int[] visited, int i) {
        for(int j=0;j<M.length;j++){
            //搜索该同学认识的所有学生
            if(M[i][j]==1 && visited[j]==0){
                visited[j] = 1; //访问过设为1
                dfsSolver(M,visited,j);
            }
        }
    }


    //方法二：使用BFS
    public int findCircleNumA(int[][] M) {
        int[] visited=new int[M.length];
        int count=0;

        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<M.length;i++){
            if (visited[i]==0){
                //该同学未访问
                queue.add(i);
                while (!queue.isEmpty()){
                    int s=queue.remove();
                    visited[s]=1;
                    for(int j=0;j<M.length;j++){
                        if (M[s][j]==1 && visited[j]==0){
                            //s同学认识的学生 且未被访问过，则加入队列
                            queue.offer(j);
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }

    //方法三：并查集
    public int findCircleNumB(int[][] M) {
        int[] parent = new int[M.length];
        Arrays.fill(parent, -1);
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {
                if (M[i][j] == 1 && i != j) {
                    //认识的同学 若不属于一个朋友圈，则合并
                    union(parent, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == -1) {
                count++;
            }
        }
        return count;
    }

    public int find(int[] parent ,int i){
        if(parent[i]==-i){
            return i;
        }
        return find(parent,parent[i]);
    }

    public void union(int[] parent,int a,int b){
        int x=find(parent,a);
        int y=find(parent,b);
        if (x!=y){
            parent[x]=y;
        }
    }
}
